// ===========   File : ListQueue.c =============//

#include <stdio.h>
#include <stdlib.h>
#include "ListQueue.h"

/* 
    构造函数
*/
LinkedListQueue *NewLinkedListQueue(void)
{
    LinkedListQueue *queue = (LinkedListQueue*)malloc(sizeof(LinkedListQueue));
    queue->front = NULL;
    queue->rear = NULL;
    queue->queSize = 0;

    return queue;
}

/* 构造函数: 实际上就是创建一个节点 */
ListNode *NewListNode(int val)
{
    ListNode *node;
    node = (ListNode*)malloc(sizeof(ListNode));
    node->val = val;
    node->next = NULL;
    return node;
}


/* 析构函数 */
void DelLinkedListQueue(LinkedListQueue *queue)
{
    /* 释放所有节点 */
    for(int i=0;i<queue->queSize && queue->front != NULL;i++)
    {
        ListNode *temp = queue->front;
        queue->front = queue->front->next;
        free(temp);
    }

    /* 释放queue结构体 */
    free(queue);
}

/* 获取队列的长度 */
int ListQueueSize(LinkedListQueue *queue)
{
    return queue->queSize;
}

/* 判断是否为空 */
_Bool ListQueueEmpty(LinkedListQueue *queue)
{
    return (ListQueueSize(queue) == 0);
}

/* 入队 */
void ListQueuePush(LinkedListQueue *queue,int num)
{
    /* 尾节点添加node */
    ListNode *node = NewListNode(num);

    /* 如果队列为空，则令头尾节点都指向该节点 */
    if(queue->front == NULL ) {
        queue->front = node;
        queue->rear = node;
    }
    /* 如果队列不为空，则将尾节点指向这个节点 */
    else {
        // 将新节点挂在上个节点的后面
        queue->rear->next=node;
        // 将新节点挂在队列下一个的钩子上，用于下次新节点有挂的地方
        queue->rear=node;
    }

    queue->queSize++;
}

/* 访问对列首元素 */
int ListQueuePeek(LinkedListQueue *queue)
{
    assert(ListQueueSize(queue) && queue->front);
    return queue->front->val;
}

/* 出队 */
void ListQueuePop(LinkedListQueue *queue)
{
    int num = ListQueuePeek(queue);
    ListNode *tmp = queue->front;
    /*
    第一个node的front，rear是同一个指针，在push的时候queue->rear->next=node;将front的next挂上了下一个node
    因为这里将下一个node挂在了front上，并且释放第一个node，以此类推
    */
    queue->front = queue->front->next;
    free(tmp);
    queue->queSize--;
}

/* 打印队列 */
void PrintLinkedListQueue(LinkedListQueue *queue)
{
    int arr[queue->queSize];
    //拷贝链表的数据到数组
    int i;
    
    ListNode *node = queue->front;
    
    for(i=0;node != NULL && i<queue->queSize;i++) {
        
        arr[i] = node->val;
        node = node->next;
    }
    
    if(!queue->queSize) {
        printf("队列为空\r\n");
        return ;
    }
    for(i=0;i<queue->queSize;i++) {
        printf("arr[%d]:%d\r\n",i,arr[i]);
    }
    
}

/*
    测试用的main函数
*/
void main(int argc, char * argv[] )
{
    printf("*******************   创建一个队列,打印队列基本信息   **************************\r\n");
    LinkedListQueue *myqueue = NewLinkedListQueue();
    PrintLinkedListQueue(myqueue);

    printf("*******************   第一次:创建一个节点并添加进队列里面   **************************\r\n");
    ListQueuePush(myqueue,100);
    PrintLinkedListQueue(myqueue);

    printf("*******************   第二次:创建一个节点并添加进队列里面   **************************\r\n");
    ListQueuePush(myqueue,200);
    PrintLinkedListQueue(myqueue);

    printf("*******************   第三次:创建一个节点并添加进队列里面   **************************\r\n");
    ListQueuePush(myqueue,300);
    PrintLinkedListQueue(myqueue);

    printf("*******************   第一次:访问队首元素   **************************\r\n");
    int num = ListQueuePeek(myqueue);
    printf("队首元素：%d\r\n",num);

    printf("*******************   第一次:出队并重新遍历队列   **************************\r\n");
    ListQueuePop(myqueue);
    PrintLinkedListQueue(myqueue);

    printf("*******************   第二次:访问队首元素   **************************\r\n");
    num = ListQueuePeek(myqueue);
    printf("队首元素：%d\r\n",num);
    
    printf("*******************   第二次:出队并重新遍历队列   **************************\r\n");
    ListQueuePop(myqueue);
    PrintLinkedListQueue(myqueue);

    printf("*******************   第三次:访问队首元素   **************************\r\n");
    num = ListQueuePeek(myqueue);
    printf("队首元素：%d\r\n",num);

    printf("*******************   第三次:出队并重新遍历队列   **************************\r\n");
    ListQueuePop(myqueue);
    PrintLinkedListQueue(myqueue);

    printf("*******************   析构队列   **************************\r\n");
    DelLinkedListQueue(myqueue);
    printf("*******************   析构队列完成   **************************\r\n");

}
